#include "sort.h"
#include "stdlib.h"
#include "stdint.h"
#include "string.h"

/*
归并排序，时间稳定，空间稳定
qsort可能会导致栈溢出
*/
void mergeAdd(struct merge_list_t* merge_list, int left, int mid, int right) {
  int size = merge_list->size;
  int i = left;

  int j = mid + 1;
  int k = left;  //临时下标
  while (i <= mid && j <= right) {
    if (((*merge_list->cmp)((uint8_t*)merge_list->data + i * size, (uint8_t*)merge_list->data + j * size)) < 0) {
      memcpy((uint8_t*)merge_list->buf + k * size, (uint8_t*)merge_list->data + i * size, size);
      k++;
      i++;
    } else {
      memcpy((uint8_t*)merge_list->buf + k * size, (uint8_t*)merge_list->data + j * size, size);
      k++;
      j++;
    }
  }
  if (i <= mid) {
    memcpy((uint8_t*)merge_list->buf + k * size, (uint8_t*)merge_list->data + i * size, (mid - i + 1) * size);
    k += (mid - i + 1);
    i += (mid - i + 1);
  }
  if (j <= right) {
    memcpy((uint8_t*)merge_list->buf + k * size, (uint8_t*)merge_list->data + j * size, (right - j + 1) * size);
    k += (right - j + 1);
    j += (right - j + 1);
  }
  memcpy((uint8_t*)merge_list->data + left * size, (uint8_t*)merge_list->buf + left * size, size * (right - left + 1));
}




void mergeSort(struct merge_list_t* merge_list) {
  if (merge_list->data == NULL || merge_list->buf == NULL || merge_list->cmp == NULL || merge_list->num <= 1 ||
      merge_list->size <= 0) {
    return;
  }
  //定义一个步长gap，初始值为1，相当于每次只合并两个长度为1的元素
  int step = 1;
  int len = merge_list->num;
  while (step <= len) {
    for (int i = 0; i <= len - step - 1; i += 2 * step) {
      int beg = i;
      int mid = (step - 1) + i;
      if (mid >= len - 1) {
        mid = len - 1;
      }
      int end = mid + step;
      if (end >= len - 1) {
        end = len - 1;
      }
      mergeAdd(merge_list, beg, mid, end);
    }
    step = step << 1;
  }
}




int cmp_u8(const void* a, const void* b) {
  return *(uint8_t*)a > *(uint8_t*)b ? 1 : -1;
}
int cmp_u16(const void* a, const void* b) {
  return *(uint16_t*)a > *(uint16_t*)b ? 1 : -1;
}
int cmp_u32(const void* a, const void* b) {
  return *(uint32_t*)a > *(uint32_t*)b ? 1 : -1;
}
int cmp_i32(const void* a, const void* b) {
  return *(int32_t*)a > *(int32_t*)b ? 1 : -1;
}
int cmp_float(const void* a, const void* b) {
  return *(float*)a > *(float*)b ? 1 : -1;
}
int cmp_double(const void* a, const void* b) {
  return *(double*)a > *(double*)b ? 1 : -1;
}




